from typing import *


class Solution:

    def frogPosition(self, n: int, edges: List[List[int]], t: int,
                     target: int) -> float:
        nexts = [[] for _ in range(n + 1)]
        for a, b in edges:
            nexts[a].append(b)
            nexts[b].append(a)
        q = Deque([(1, 1, 0)])
        visit = [False] * (n + 1)
        visit[1] = True
        while q:
            p, g, ti = q.popleft()
            if ti > t:
                return 0
            if p == target:
                if t == ti:
                    return g
                for nxt in nexts[p]:
                    if not visit[nxt]:
                        return 0
                return g
            plus = len(nexts[p]) if p == 1 else len(nexts[p]) - 1
            ng = g * (1 / plus) if plus != 0 else g
            for nxt in nexts[p]:
                if not visit[nxt]:
                    visit[nxt] = True
                    q.append((nxt, ng, ti + 1))
